1. Field of the Invention
The present invention relates to signal processing and more particularly to direct and fast Fourier transformations of the 12-point-transform type. The invention further relates to an arrayable, fast-Fourier transformer for accommodating radix-12 transformations at very high speed, over very short epoch times, with minimum system energy expenditure per transform point.
2. Related Technical Art
Direct Fourier Transform (DFT) and Fast Fourier Transform (FFT) signal processors are used in many advanced signal-processing applications requiring analysis of large quantities of sensor data in short time periods. Such applications include signal analysis for target, object, or geographical body recognition; compensating for transfer aberrations in communication signals; and optical data processing. In order to be useful in these and other applications, DFT or FFT signal processors must accommodate large numbers of transforms, or amounts of data, using very short epoch times for processing.
Exemplary requirements or features for advanced signal analysis applications include FDM/TDM signal translation for communication or data processing requiring about 2000 points in 100 .mu.s, and satellite based processor functions ranging from 1000 points in 1.2 .mu.s up to 4000 points in 100 .mu.s. Real-Time image processing typically requires on the order of 1000 data points to be processed in epoch time periods of about 8 .mu.s.
Aside from the speed or data-throughput requirements, power consumption is a major concern for many applications. Power may be supplied by portable generation or storage equipment, such as in space borne processing, where the ultimate power available is limited by many considerations. In such power limited applications, signal processor power consumption must be as low as possible. In addition, larger power consumption also implies larger power dissipation in terms of heat which is also critical to many processor designs. Therefore, new DFT and FFT designs seek to reduce the power consumption per transform per epoch.
Unfortunately, a key problem with any FFT processor is the amount of energy consumed per transform point. Generally high-performance, efficient FFT processors exhibit energy dissipations per transform point in the range of 100 to 1000 times log.sub.2 N nanojoules, where N is the number of points in a given transform. As a consequence, reasonably large transforms required to process large amounts or arrays of data in real time, result in a large power consumption.
Several techniques have been developed in the art to increase the efficiency of the DFT and FFT algorithms or computations in order to reduce the power consumption, as well as provide more efficient circuit structures. One design technique is to create multiply-free computation sub-elements or building blocks which are used to form the desired FFT and increase the computational efficiency. Decreasing the number of multiplications decreases the number of computations required to execute an overall DFT or FFT algorithm. At the same time, there is a corresponding savings in power dissipation from performing fewer computations as well as decreased circuit complexity for associated data transfer, accumulation, and storage elements. Decreasing multiplication operations, especially for complex data, also provides direct manufacturing cost benefits for the circuits, or software, which implement DFT or FFT algorithms and may increase operational reliability.
The Cooley-Tukey radix-2 FFT algorithm, published in 1965, represents the first step in the multiply-free approach, which was advanced in 1966 to a more efficient radix-4 architecture. In 1967, Charles Radar extended this work to a highly efficient, but not multiply-free, radix-8 structure, and in 1978 the radix-3 multiply-free FFT architecture was developed by Dubois and Vetsanopolis, see "A New Algorithm For The Radix-3 FFT," IEEE TRANS. VOL. ASSP-26, No. 3, June 1978, pp 222-225. At this point, efficient DFT or FFT analysis could be obtained in powers-of-three and not just powers-of-two. Large FFT or DFT algorithms could now be accommodated more efficiently because the number of total computations required was reduced. However, the radix-3 architecture does require extension into a non-orthogonal coordinate, skew-complex, system in which the radix-4 is no longer multiply free, which limits the overall efficiency for larger FFT point sizes. Finally, in 1981, Prakash and Rao in India introduced a multiply-free radix-6 FFT architecture which increases efficiency over using a combination of radix2/radix-3 structures for the radix-6 algorithm, see "A New Radix-6 FFT Algorithm," IEEE TRANS. VOL. ASSP-29, No. 4, August 1981, pp 939-941.
All of these DFT/FFT architectures allow less complex addressing and control and provide improved computational efficiency due to decreased multiplication requirements. However, as previously indicated, modern signal and data processing requirements call for very large numbers of data and very large DFT or FFT point sizes. While the present state of the art is an improvement, a large number of very small building blocks, and, thus, inter-block transfer computations is still required. It would be useful to have larger point or radix size building blocks into which the very large FFT/DFT algorithms could be efficiently sub-divided. Even though theoretical analysis projects diminishing returns, less decrease per radix size increase, on efficiency beyond the current building block sizes, every increase in efficiency is useful for many power limited applications. In addition, larger more efficient FFT building blocks may have manufacturing and other cost benefit advantages not associated with the theoretical efficiency and not readily apparent to the art.
Therefore, what is needed is a larger radix DFT/FFT building block which is more computationally efficient than the current computational combinations (blocks). It would be an advantage if the new building block architecture employed a very minimum number of multiplications or multipliers with the least amount of complexity in design.